# Author    :Dun_Hz
# Time      :2024/3/11 10:39
from collections import deque

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None


e = BiTreeNode('E')
a = BiTreeNode('A')
g = BiTreeNode('G')
c = BiTreeNode('C')
f = BiTreeNode('F')
b = BiTreeNode('B')
d = BiTreeNode('D')

e.lchild = a
a.rchild = c
c.lchild = b
c.rchild = d
e.rchild = g
g.rchild = f

def pre_order(root):
    if root:
        print(root.data, end=' ')
        pre_order(root.lchild)
        pre_order(root.rchild)
def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end=' ')
        in_order(root.rchild)
def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end=' ')

def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue)>0:
        node = queue.popleft()
        print(node.data, end = ' ')
        # 从左到右，先进先出
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)


root = e
pre_order(root)
print('')
in_order(root)
print('')
post_order(root)
print('')
level_order(root)